package org.example.datastructure.ch6;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class HfTree {
    LinkedList<Node> list;
    Node root;
    List<String> res;
    public HfTree(){}
    public HfTree(String str,int[] w){
        list = new LinkedList<>();
        int n = w.length;
        for(int i=0;i<n;i++){
            list.add(new Node(str.charAt(i),w[i]));
        }
    }
    private void create(){
        Collections.sort(list,(a,b)->a.weight-b.weight);
        int n = list.size();
        while(n>1){
            Node max1 = list.poll();
            Node max2 = list.poll();
            n=n-2;
            Node newNode = new Node(max1.weight+max2.weight);
            newNode.left = max2;
            newNode.right = max1;
            int i = 0;
            while(i<n&&newNode.weight>list.get(i).weight){
                i++;
            }
            if(i< n){
                list.add(i,newNode);
            } else {
                list.add(newNode);
            }
            n++;
        }
        root = list.get(0);
    }
    public List<String> getCode(){
        create();
        res = new ArrayList<>();
        dfs(root,"");

        return res;
    }
    void dfs(Node rot,String co){
        if(rot.left==null&&rot.right==null){
            co = co+rot.data;
            res.add(co);
            return;
        }
        dfs(rot.left,co+"0");
        dfs(rot.right,co+"1");
    }
}

class Node{
    char data;
    int weight;
    Node left, right;
    public Node(){}
    public Node(int weight){
        this.weight = weight;
        left = null;
        right = null;
    }
    public Node(char data,int weight){
        this.data = data;
        this.weight = weight;
        left = null;
        right = null;
    }

    @Override
    public String toString() {
        return ""+ weight;
    }
}